% small.tex
\documentclass{beamer}
\usetheme{Copenhagen}

\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{cancel}
\usepackage{umoline}
\usepackage{ulem}
\usepackage{lmodern}

\title{Clustering}
\author{Carlos Colmenares \and Kelwin Fernández}
\institute[UMBC]{
  Universidad Simón Bolívar, Sartenejas\\
  Diseño de Algoritmos II - CI5652\\[1ex]

}
\date{Junio, 2011}

\begin{document}

%--- the titlepage frame -------------------------%
\begin{frame}[plain]
  \titlepage
\end{frame}

\begin{frame}{Programa}
\tableofcontents
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Definición}

\begin{frame}{Definición}

\begin{block}{Definición Informal}
El problema de clustering consiste en realizar una partición de un
conjunto, cuyos elementos son observaciones de algún tipo, de tal manera que los elementos en cada subconjunto
de la partición se asemejen unos a otros de cierta manera, mientras que los elementos
en subconjuntos distintos deben parecerse lo menos posible.
\end{block}
\end{frame}

\begin{frame}{Definición Formal}

\begin{itemize}
\item Sea $D$ un conjunto de observaciones.
\item Sea $\Pi(D)$ el conjunto de todas las particiones de $D$.
\item Sea $\Pi_k(D)$ el conjunto de todas las \emph{k-particiones}
de $D$, donde una \emph{k-partición} es una partición de un conjunto en 'k' partes.
\item Sea $f: \Pi(D) \rightarrow \mathbb{R}$ una función que mida la \emph{bondad} \footnote{Refiérase a la sección
\ref{CalidadSolucion} para un mayor análisis de dicha función de bondad} de una partición, donde una partición $A$ es mejor que otra $B$
si y sólo si $f(A) > f(B)$.

\end{itemize}

\begin{block}{Definición}
El problema general de Clustering consistirá entonces en conseguir una partición $p \in \Pi(D)$ tal que:

$$ \forall q \in \Pi(D), f(q) \le f(p) $$
\end{block}

\end{frame}

\section{Tipos de Clustering}

\begin{frame}{Tipos de Clustering}

\begin{itemize}
\item \textbf{Numérico.}
\item Categórico.
\item Combinados.
\end{itemize}
\end{frame}

\section{Calidad de una solución}

\begin{frame}{Calidad de una solución}
\begin{block}{Distancia Intra-Cluster}
Es una medida del nivel se ``semejanza'' entre los puntos
que pertenecen a un cluster.
\end{block}

\begin{itemize}
  \item \textbf{Promedio de distancias:}
    Se define como el promedio de la distancia entre el centroide de un cluster
    y todos los puntos que pertenecen a éste.

    $$\sigma_i = \frac{1}{|D_{c_i}|} \displaystyle\sum\limits_{\vec{x} \in D_{c_i}} d(c_i,\vec{x}) $$

  \item \textbf{Distancia máxima:}
    Se define como la máxima distancia entre el centroide de un cluster y cualquiera de sus puntos.

    $$\sigma_i = \max\limits_{\vec{x} \in D_{c_i} } d(c_i,\vec{x}) $$
\end{itemize}

\end{frame}

\begin{frame}{Bondad de una solución}
\begin{block}{Distancia Inter-Cluster}
Es una medida del nivel de ``semejanza'' o ``cercanía'' entre
dos clusters.
\end{block}

\begin{itemize}
  \item \textbf{Distancia entre centroides:}

    $$h(D_{c_i},D_{c_j}) = d(c_i,c_j)$$

  \item \textbf{Promedio de distancias:}
    Corresponde al promedio de la distancia entre los puntos de ambos clusters, formalmente:

    $$h(D_{c_i},D_{c_j}) = \frac{1}{|D_{c_i}||D_{c_j}|} \displaystyle\sum\limits_{\vec{x} \in D_{c_i}, \vec{y} \in D_{c_j}} d(\vec{x},\vec{y}) $$

\end{itemize}

\end{frame}

\begin{frame}{Funciones de bondad}
\begin{itemize}
  \item \textbf{Método de Davies–Bouldin: }

    $$f( S_D(C) ) = \frac{1}{n} \displaystyle\sum\limits_{i=1}^n \left ( \max\limits_{1 \le j \le n, i \ne j} \frac{\sigma_i+\sigma_j}{h(D_{c_i},D_{c_j})}\right ) $$

  \item \textbf{Método de Dunn:}

    $$f( S_D(C) ) = \frac{ \min\limits_{1 \le i,j \le n,\ i \ne j} h(D_{c_i},D_{c_j})} { \max\limits_{1 \le k \le n} \sigma_k } $$

\end{itemize}
\end{frame}

\section{Operadores de Vecindad}

\begin{frame}{Operadores de Vecindad}
\begin{itemize}
    \item \textbf{Aproximación de centroides}.\vspace{1cm}
    \item \textbf{Aproximación suave de centroides}.
\end{itemize}

\bigskip
\begin{block}{Tamaño de las Vecindades}
Si tenemos $N$ datos y $k$ clusters, ambos operadores tendrán
vecindades de tamaño $k\cdot N$.
\end{block}

\end{frame}

\section{Metaheurísticas Implementadas}

\begin{frame}{Metaheurísticas Implementadas}
\begin{itemize}
\item Local Search.
\item Iterated Local Search.
\item Tabu Search.
\item Variable Neighborhood Search.
\item \alert{k-means}.
\end{itemize}
\end{frame}

\begin{frame}{Algoritmo de las k-medias (k-means)}

\texttt{
\hspace{-0.2cm}( 1) proc k\_means():\\
( 2)     \hspace{0.5cm}S <- solución\_Inicial()\\
( 3)     \hspace{0.5cm}S* <- S\\
( 4)     \hspace{0.5cm}mientras( no criterio\_de\_parada ) hacer\\
( 5)     \hspace{0.5cm}\hspace{0.5cm}    asignar\_centroide\_mas\_cercano(S)\\
( 6)     \hspace{0.5cm}\hspace{0.5cm}    S <- recomputar\_centroides(S)\\
( 7)     \hspace{0.5cm}\hspace{0.5cm}    si criterio\_de\_aceptación(S*,S) entonces\\
( 8)     \hspace{0.5cm}\hspace{0.5cm}\hspace{0.5cm}        S* <- S\\
( 9)     \hspace{0.5cm}\hspace{0.5cm}    fin\_si\\
(10)     \hspace{0.5cm}fin\_mientras\\
(11)     \hspace{0.5cm}retornar S*\\
(12) fin\_proc\\
}

\end{frame}

\section{Resultados}

\begin{frame}{Iris}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Iris}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.3173 & 0.1297 & 0.2526 & 0.0132 & 2.43\\
\hline
ILS & 0.2977 & \textbf{0.1129} & 0.1981 & 0.1394 & 1000.0\\
\hline
TS & \textbf{0.2545} & 0.1332 & \textbf{0.1962} & 10.0239 & 19.0\\
\hline
VNS & 0.3074 & 0.138 & 0.242 & 0.0115 & 2.47\\
\hline
\end{tabular}
\end{frame}

\begin{frame}{Wine}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Wine}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.462 & 0.391 & 0.4504 & 0.0124 & 3.2\\
\hline
ILS & 0.4634 & \textbf{0.2967} & 0.4167 & 0.5884 & 1000.0\\
\hline
TS & \textbf{0.4291} & 0.3391 & \textbf{0.3751} & 10.0722 & 19.0\\
\hline
VNS & 0.4634 & 0.36 & 0.4359 & 0.012 & 3.17\\
\hline
\end{tabular}
\end{frame}

\begin{frame}{Ecoli}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Ecoli}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.2197 & 0.161 & 0.186 & 0.0187 & 5.7 \\
\hline
ILS & 0.2193 & \textbf{0.1359} & 0.1854 & 1.334 & 1000.0 \\
\hline
TS & \textbf{0.1943} & 0.157 & \textbf{0.1724} & 10.1643 & 19.0 \\
\hline
VNS & 0.2105 & 0.1547 & 0.1803 & 0.0199 & 6.07 \\
\hline
\end{tabular}
\end{frame}

\begin{frame}{Círculos 1}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 1}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.2497 & 0.0886 & 0.1606 & 0.0342 & 2.67\\
\hline
ILS & 0.231 & \textbf{0.0738} & 0.1328 & 0.5955 & 1000.0 \\
\hline
TS & \textbf{0.1239} & 0.0873 & \textbf{0.0946} & 10.0901 & 19.0\\
\hline
VNS &  0.2304 & 0.0886 & 0.1359 & 0.0281 & 3.23\\
\hline
\end{tabular}
\end{frame}

\begin{frame}{Círculos 4}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 4}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.1962 & 0.0545 & 0.1405 & 0.0562 & 4.2\\
\hline
ILS & 0.1895 & 0.0545 & 0.1242 & 1.9969 & 1000.0\\
\hline
TS & \textbf{0.1611} & \textbf{0.045} & \textbf{0.1005} & 10.2218 & 19.0\\
\hline
VNS & 0.1795 & 0.0545 & 0.1236 & 0.0609 & 4.0\\
\hline
\end{tabular}
\end{frame}

\begin{frame}{Círculos 5}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 5}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.152 & 0.0783 & 0.1169 & 0.0548 & 3.2\\
\hline
ILS & \textbf{0.1402} & 0.0783 & 0.1091 & 1.9318 & 1000.0\\
\hline
TS & \textbf{0.1402} & 0.0783 & \textbf{0.1018} & 10.1956 & 19.0\\
\hline
VNS & 0.1403 & \textbf{0.0782} & 0.1129 & 0.0526 & 4.07\\
\hline
\end{tabular}
\end{frame}

\begin{frame}{Círculos 6}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\multicolumn{6}{|c|}{\textbf{Círculos 6}}\\
\hline
 & Peor & Mejor & Promedio & T$_{prom}(seg)$ & \#Iter$_{prom}$\\
\hline
LS & 0.1712 & 0.0906 & \textbf{0.1136} & 0.054 & 4.1\\
\hline
ILS & 0.1664 & 0.0906 & 0.1358 & 2.1301 & 1000.0\\
\hline
TS & \textbf{0.1639} & \textbf{0.0874} & 0.1196 & 10.2235 & 19.0 \\
\hline
VNS & 0.1712 & 0.0905 & 0.1282 & 0.0606 & 4.47 \\
\hline
\end{tabular}
\end{frame}

\begin{frame}{Local Search}
\begin{center}
\includegraphics[scale=0.2]{LS/s1/circulos.jpg}
\end{center}
\end{frame}

\begin{frame}{Local Search}
\begin{center}
\includegraphics[scale=0.2]{LS/s1/circulossol.jpg}
\end{center}
\end{frame}

\begin{frame}{Local Search}
\begin{center}
\includegraphics[scale=0.2]{LS/s2/circulos.jpg}
\end{center}
\end{frame}

\begin{frame}{Local Search}
\begin{center}
\includegraphics[scale=0.2]{LS/s2/circulossol.jpg}
\end{center}
\end{frame}

\begin{frame}{Local Search}
\begin{center}
\includegraphics[scale=0.2]{LS/s1/circulos.jpg}
\end{center}
\end{frame}

\begin{frame}{Local Search}
\begin{center}
\includegraphics[scale=0.2]{LS/s1/circulossol.jpg}
\end{center}
\end{frame}

\begin{frame}{Iterated Local Search}
\begin{center}
\includegraphics[scale=0.2]{ILS/s1/circulos.jpg}
\end{center}
\end{frame}

\begin{frame}{Iterated Local Search}
\begin{center}
\includegraphics[scale=0.2]{ILS/s1/circulossol.jpg}
\end{center}
\end{frame}

\begin{frame}{Iterated Local Search}
\begin{center}
\includegraphics[scale=0.2]{ILS/s2/circulos.jpg}
\end{center}
\end{frame}

\begin{frame}{Iterated Local Search}
\begin{center}
\includegraphics[scale=0.2]{ILS/s2/circulossol.jpg}
\end{center}
\end{frame}

\begin{frame}{Variable Neighborhood Search}
\begin{center}
\includegraphics[scale=0.2]{VNS/s1/salida.jpg}
\end{center}
\end{frame}

\begin{frame}{Variable Neighborhood Search}
\begin{center}
\includegraphics[scale=0.2]{VNS/s1/salidasol.jpg}
\end{center}
\end{frame}

\begin{frame}{Tabu Search}
\begin{center}
\includegraphics[scale=0.2]{TS/s5/salida.jpg}
\end{center}
\end{frame}

\begin{frame}{Tabu Search}
\begin{center}
\includegraphics[scale=0.2]{TS/s5/salidasol.jpg}
\end{center}
\end{frame}

\begin{frame}{Tabu Search}
\begin{center}
\includegraphics[scale=0.2]{TS/s6/salida.jpg}
\end{center}
\end{frame}

\begin{frame}{Tabu Search}
\begin{center}
\includegraphics[scale=0.2]{TS/s6/salidasol.jpg}
\end{center}
\end{frame}

\end{document}
